//给定一个含有 n 个正整数的数组和一个正整数 target 。 
//
// 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返
//回其长度。如果不存在符合条件的子数组，返回 0 。 
//
// 
//
// 示例 1： 
//
// 
//输入：target = 7, nums = [2,3,1,2,4,3]
//输出：2
//解释：子数组 [4,3] 是该条件下的长度最小的子数组。
// 
//
// 示例 2： 
//
// 
//输入：target = 4, nums = [1,4,4]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：target = 11, nums = [1,1,1,1,1,1,1,1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target <= 10⁹ 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= 10⁵ 
// 
//
// 
//
// 进阶： 
//
// 
// 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 
// 
//
// Related Topics 数组 二分查找 前缀和 滑动窗口 👍 2001 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2023-12-20 22:15:15
 * @description 209.长度最小的子数组
 */
public class MinimumSizeSubarraySum{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MinimumSizeSubarraySum().new Solution();
		  solution.minSubArrayLen(7,new int[]{2,3,1,2,4,3});
		 solution.minSubArrayLen(15,new int[]{1,2,3,4,5});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //二分+前缀和
    public int minSubArrayLen1(int target, int[] nums) {
		int len = nums.length;
		int [] sum=new int[len+1];
		//前缀和
		for (int i = 1; i <=len; i++) {
			sum[i]=nums[i-1]+sum[i-1];
		}
		if(sum[len]<target) return 0;
		int l=0,r=len;
		while (l<r){
			int m=l+(r-l)/2;
			if(isPresent(sum,target,m)){
				r=m;
			}else {
				l=m+1;
			}
		}

		return l;
    }
	//  1 2 3
	public boolean isPresent(int []sum,int k,int m){
		for (int i = m; i <sum.length; i++) {
			if(sum[i]-sum[i-m]>=k){
				return true;
			}
		}
		return false;
	}

	//二分前缀和，
	public int minSubArrayLen2(int s, int[] nums) {
		int n = nums.length;
		if (n == 0) {
			return 0;
		}
		int ans = Integer.MAX_VALUE;
		int[] sums = new int[n + 1];
		// 为了方便计算，令 size = n + 1
		// sums[0] = 0 意味着前 0 个元素的前缀和为 0
		// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
		// 以此类推
		for (int i = 1; i <= n; i++) {
			sums[i] = sums[i - 1] + nums[i - 1];
		}
		for (int i = 1; i <= n; i++) {
			int target = s + sums[i - 1];
			//java中如果没有搜索到
			// 这个负值表示搜索键应该插入数组的位置，负值的计算方式是取负后再减1。
			//return -(low + 1);  // key not found.  源码
			int bound = Arrays.binarySearch(sums, target);
			if (bound < 0) {
				bound = -bound - 1;
			}
			if (bound <= n) {
				ans = Math.min(ans, bound - (i - 1));
			}
		}
		return ans == Integer.MAX_VALUE ? 0 : ans;
	}
		//滑动窗口
	public int minSubArrayLen(int s, int[] nums) {
		int sum=0,res=nums.length+1;
		int l=0,r=0;
		while (r<nums.length){
				sum+=nums[r];
				while (sum>=s){
					res=Math.min(r-l+1,res);
					sum-=nums[l++];
				}
			r++;
		}
		return res==nums.length+1?0:res;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
